package com.paso;

import sun.net.www.protocol.http.HttpURLConnection;

/**
 * 单链表
 * 1.链表由一个一个节点组成，每个节点包含数据 和 next域 两部分
 * 2.头节点不存放数据，有next域，next为null时表示空链表
 * 3.头节点作用就是表示单链表的头
 * <p>
 * 第一种添加操作：
 * 1.先定义一个链表的头节点
 * 2.往链表的尾部添加节点
 */

public class SingleLinkedListDemo {
    public static void main(String[] args) {

        // 定义节点
        HeroNode heroNode1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode heroNode2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode heroNode3 = new HeroNode(3, "吴用", "智多星");
        HeroNode heroNode4 = new HeroNode(4, "林冲", "豹子头");

        // 定义单向链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();


        // 添加节点
//        singleLinkedList.add(heroNode1);
//        singleLinkedList.add(heroNode2);
//        singleLinkedList.add(heroNode4);
//        singleLinkedList.add(heroNode3);


        // 按照顺序添加节点

        singleLinkedList.addByOrder(heroNode2);
        singleLinkedList.addByOrder(heroNode4);
        singleLinkedList.addByOrder(heroNode1);
        singleLinkedList.addByOrder(heroNode3);
        singleLinkedList.addByOrder(heroNode3);

        singleLinkedList.list();

        HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~~");
        singleLinkedList.update(newHeroNode);

        // 打印所有节点
        System.out.println("修改之后的链表");
        singleLinkedList.list();


        singleLinkedList.delete(1);
        System.out.println("删除一个节点之后的链表");
        singleLinkedList.list();


        // 测试；求链表的有效节点的个数
        int length = getLength(singleLinkedList.getHead());
        System.out.println("链表的有效节点的个数=" + length);


        // 求链表的倒数第index个节点
        int index = 1;
        HeroNode indexNode = findIndexNode(singleLinkedList.getHead(), index);
        System.out.println("求链表的倒数第" + index + "个节点是" + indexNode);


        System.out.println("反转链表");
        reverse(singleLinkedList.getHead());
        singleLinkedList.list();
    }






    /**
     * 反转链表
     *
     * @param head 原始链表的头
     * @return 反转后的链表
     */
    public static void reverse(HeroNode head) {

        // 校验链表是否为空或者只有一个有效节点
        if (head.getNext() == null || head.getNext().getNext() == null){
            return;
        }

        // 定义一个辅助变量
        HeroNode curr = head.getNext();

        // 指向当前节点[curr]的下一节点
        HeroNode next = null;

        // 定义一个反转后的链表的头
        HeroNode reverseHead = new HeroNode(0, "", "");

        // 遍历原始链表
        while (curr != null) {

            // 先暂时保持当前节点的下一个节点，因为后面需要使用
            next = curr.getNext();


            // 将curr链接到新的链表上
            curr.setNext(reverseHead.getNext());

            // 将新的链表链接到curr上
            reverseHead.setNext(curr);

            // curr后移
            curr = next;
        }

        // 把原始的头指向新的链表的第一个有效节点
        head.setNext(reverseHead.getNext());

    }

    /**
     * 求链表的倒数第index个节点
     *
     * @param head  需要查找的链表的头节点
     * @param index 需要查找的节点的倒数序号
     * @return 查询到的节点，没有就返回null
     */
    public static HeroNode findIndexNode(HeroNode head, int index) {
        // 校验头节点
        if (head.getNext() == null) {
            return null;
        }

        // 第一个遍历得到链表的长度
        int length = getLength(head);

        // 对index 做一个校验
        if (index <= 0 || index > length) {
            return null;
        }

        // 定义一个辅助变量
        HeroNode temp = head.getNext();

        // 遍历链表 for循环 length - index 次
        for (int i = 0; i < length - index; i++) {
            temp = temp.getNext();
        }

        return temp;
    }


    /**
     * 求出链表的有效节点的个数（如果有头节点，不统计头节点）
     *
     * @param head 链表的头节点
     * @return 有效节点的个数
     */
    public static int getLength(HeroNode head) {
        if (head.getNext() == null) {
            return 0;
        }

        HeroNode temp = head.getNext();
        int length = 0;
        while (temp != null) {
            length++;
            temp = temp.getNext();
        }

        return length;
    }


}
